Multicast communication can be used for the transmission of data in both a one-to-many situation (for example multimedia applications, tickertape feeds or bulk file transfer) or the many-to-many communication of data (for example conferencing or network gaming), and is increasingly gaining in importance with the deployment of multicast in the internet and with the increasing number of satellites. In FIG. 1, the schematic overview of a one-to-many multicast system, a sender 1 communicates data over a network 3 to a plurality of receivers 2. The network 3 could be any suitable network, such as for example, the internet, a local area network (LAN), satellite network, etc. The number of receivers 2 will depend on the particular multicast application, from just a few to possibly even millions of receivers, such as for cable-TV delivery, satellite or other wireless communication services. The number of receivers 2 also varies dynamically during a multicast transmission as receivers leave or join the multicast group.
In reliable multicast, used to guarantee the delivery of data to a group of receivers, feedback messages (FBMs) are returned from the receivers to either acknowledge correct receipt of data (positive acknowledgement messages known as ACKs), or loss of data (negative acknowledgement messages known as NACKs). In reliable multicast, therefore, a large group of receivers can generate a large number of feedback messages. If the multicast group size grows, the number of potential feedback messages to the sender can increase linearly, and can eventually overwhelm the sender's capacity to handle them (known as feedback implosion). Feedback implosion can cause problems due to the high concentration of network traffic at the sender, wasted bandwidth and/or high processing requirements. Feedback implosion therefore limits the ability of multicast transmission to scale to very large groups and is a major problem in reliable multicast technology.
In reliable multicast protocols which only use NACKS, a single feedback message received by the sender will be sufficient to initiate re-transmission of lost data. All other duplicate NACKs generated by the receivers are redundant and must be suppressed if feedback implosion is to be avoided. A known solution to the problem of feedback implosion involves receivers delaying before issuing repair requests (i.e. NACKs). If, in the meantime a receiver detects the same repair request has been made by another receiver then it will suppress its own repair request and stay silent. Thus, the duplication of repair requests is avoided. Each receiver can select at random the time for delaying it's repair request (known as the “backoff” time) from a timer probability distribution function, as is described below.
When a sender sends a request for feedback to the receivers, included with the request are parameters {α} and T (the timer period) for a timer probability distribution function ƒi(t), tε[0,T], i=1, . . . , R, where R is the number of receivers. (Note: the timer period T determines the time after which the backoff time periods for all receivers will have expired.) Upon receiving the request from the sender (at time τj), a receiver j which detects a data loss samples a backoff time tj from the given timer distribution function ƒj. For example, to sample a backoff time tj from an exponential timer distribution having parameters T and {α}=λ involves using a uniform random number generator to generate uniform random tu between 0 and 1, and then sampling tj from the exponential distribution as follows (the so-called inversion method),
      t    j    =            (              T        λ            )        ⁢          ln      ⁡              (                  1          +                                    (                                                ⅇ                  λ                                -                1                            )                        ×                          t              u                                      )            Receiver j waits until time τj+tj before sending its feedback to the sender, and will suppress its feedback if in the meantime it has received a duplicate feedback message (FBM) from another receiver.
Such a timer-based scheme for multicast feedback has been described by J. Nonnenmacher & E. W. Biersack in “Scaleable Feedback for Large Groups” (IEE\ACM Trans. Networking, vol 7, pp 375-386, June 1999). Nonnenmacher and Biersack discussed probabilistic feedback methods in relation to three different forms of timer function: a uniformly distributed timer function, beta-distributed timer function and exponentially distributed timer function. Comparisons of the three timer functions concluded that the best feedback suppression was achieved using the exponentially distributed timer function.
However, one problem with the timer-based approach described above to suppress multicast feedback is that an extra latency is introduced (i.e. extending the period of time taken before the sender receives the first repair request), due to the random times that the receivers delay their responses. There exists a trade-off between the data delivery latency versus the amount of NACK suppression (and consequently the ability to scale the multicast to a larger group). Accordingly, a timer distribution function suitable for use with one particular multicast application may be entirely unsuitable for use with another multicast application, due to the varying scalability and latency requirements. For example, multimedia applications can require both scalability and low latency. Low latency is also a requirement for collaborative applications such as data-conferences (whiteboarding), although the scaling requirements are more modest (less than 100 participants). Collaborative applications like this will require, for example, latency of less than 400 msec so that responses do not cause discomfort to the human participants. Message streaming applications such as tickertape and news feeds often require both low latency and scalability to thousands (or possibly millions) of receivers. Tickertape feeds to brokerage houses need to be particularly timely because the information loses value greatly as time passes, and there is also the need for strict reliability.
In contrast, bulk data delivery may have no specific latency requirement, and can be scheduled for delivery during the night when the traffic on a network is reduced. Strict reliability is usually the main concern for this application, with the need to ensure that a complete set of data is transferred correctly. However, even in bulk data delivery applications, it can sometimes be necessary to receive the data almost immediately, and therefore the latency requirements can vary widely.